#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * @brief The Solution class 410. 分割数组的最大值
 */
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        // 线性验证：
        // 把数组按照某个最大值x，进行分割，将分割数量与k之间进行比较

        // 确定x的范围
        long long left = 0, right = 0;
        for(int i=0;i<n;i++)
        {
            right += nums[i];
            if(left < nums[i])
            {
               left = nums[i]; // eg [1,2,3,4] k=3 max=4
            }
        }

        // 二分查找第一个符合要求的值
        // 0 0 1 1 1 1 1
        while(left < right)
        {
            long long mid = left + (right - left) / 2;

            if(check(nums,mid,k))
            {
                // 满足情况，继续往左找
                right = mid;
            } else
            {
                left = mid + 1;
            }
        }

        return left;
    }

    bool check(const vector<int>& nums, int x, int k)
    {
        int n = nums.size();
        long long sums = 0;
        int count = 0;
        for(int i=0;i<n;i++)
        {
            if(sums + nums[i] > x)
            {
              count++;
              sums = nums[i];
            } else {
              sums += nums[i];
            }
        }

        if(sums > 0)
        {
            count++;
        }

        return count <= k;
    }
};

//int main()
//{
//    Solution solution;
//}
